package com.fanshuai.algorithms.datastructure.linear.linkedlist;

public class ListCommonNode {

    public static boolean hasCommonNode(List list1, List list2) {
        List.Node node1 = list1.head;
        List.Node node2 = list2.head;

        while (node1 != null && node1.next != null) {
            node1 = node1.next;
        }
        while (node2 != null && node2.next != null) {
            node2 = node2.next;
        }

        return node1 == node2;
    }

    public static List.Node getCommonNode(List list1, List list2, int m, int n) {
        List.Node node1 = list1.head;
        List.Node node2 = list2.head;

        while (node1 != null && node1.next != null) {
            node1 = node1.next;
        }
        while (node2 != null && node2.next != null) {
            node2 = node2.next;
        }

        boolean commonNode = node1 == node2;
        if (!commonNode) {
            return null;
        }

        List.Node fast = null;
        List.Node slow = null;
        int k = 0;
        if (n > m) {
            k = n - m;
            fast = list2.head;
            slow = list2.head;

            while (k > 0) {
                fast = fast.next;
                k--;
            }
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
        } else {
            k = m - n;
            fast = list1.head;
            slow = list1.head;

            while (k > 0) {
                fast = fast.next;
                k--;
            }
            while (fast != null) {
                fast = fast.next;
                slow = slow.next;
            }
        }

        return slow;
    }

}
